package leetcode_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum2_40 {
	List<List<Integer>> res ;
	int n;
	int candidates[];
	
	@SuppressWarnings("unused")
	public static void main(String[] args) {
		CombinationSum2_40 solution=new CombinationSum2_40();
		//List<List<Integer>> res=solution.combinationSum2(new int[] {10,1,2,7,6,1,5}, 8) ;
		List<List<Integer>> res=solution.combinationSum2(new int[] {2,5,2,1,2}, 5) ;
	}
	
	public void help(List<Integer> values, int index, int total) {
		if(total==0) {
			List<Integer> temp=new ArrayList<Integer>();
			temp.addAll(values);
			this.res.add(temp);
		}
		else {
			for(int i=index;i<n;++i) {
				if(candidates[i]>total)
					return ;
				else if(i!=index&&candidates[i]==candidates[i-1])
					continue;
				else {
					values.add(candidates[i]);
					help(values,i+1,total-candidates[i]);
					values.remove(values.size()-1);
				}
			}
		}
	}
	
	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
	   Arrays.sort(candidates);
	   this.res=new ArrayList<List<Integer>>();
	   this.n=candidates.length;
	   this.candidates=candidates;
	   List<Integer> values=new ArrayList<Integer>();
	   help(values,0,target);
	   return this.res;
	}
}
